package bTree.LeetCode;


public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

    //归并排序来实现，算法复杂度nlogn,就是拆分成最小单位之后，2个2个排序，再排序，最终合成最长的
    public class 排序链表 {
        public ListNode sortList(ListNode head) {
            //1.先拆开,如果是一个了，那就返回了
            if (head==null||head.next == null) {
                return head;
            }
            //2.用快慢指针找到中间节点，变成两半
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != null && fast!=null&&fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            //3.将两半的头节点放进去sortList
            ListNode temp=slow.next;
            slow.next=null;
            ListNode one = sortList(head);
            ListNode two = sortList(temp);
            //4合并之后返回
            ListNode merge = merge(one, two);
            return merge;
        }

        private ListNode merge(ListNode one, ListNode two) {
            ListNode dummy=new ListNode();
            ListNode tail=dummy;
            while (one!=null&&two!=null){
                if (one.val>two.val){
                    tail.next=two;
                    two=two.next;
                }else {
                    tail.next=one;
                    one=one.next;
                }
                tail=tail.next;
            }
            if (one!=null){
                tail.next=one;
            }else {
                tail.next=two;
            }
            return dummy.next;
        }
    }
